1. Field of the Invention
The present invention relates to computer programs that use sequences of pseudo-randomly generated numbers. More specifically, the present invention provides a method to access a sequence of pseudo-randomly generated numbers to insure that each number generated and used in response to each specific call for a number in a software routine is repeatable and predictable from software version to software version.
2. Description of the Related Art
Random test generation programs have been around since the early days of microprocessor verification. These programs automate the complex job of creating large test suites necessary for the functional verification of computer systems by using random number generators to, among other things, generate test stimuli, initialize registers, pre-load caches, select operands, and the like. Those skilled in the art are well aware that the verification of modern circuit designs, especially that of large complex sequential logic designs such as a processor or an entire computer system, often takes the greater part of the resources during a design process. Design verification can be a significant bottleneck, greatly impacting the design cycle and the overall time-to-market of a new design.
In the past, processors and other complex sequential logic circuits were statically verified, meaning that verification tests were assembled from instructions, control flags, and data selected from pre-prepared tables without regard for the intermediate machine states of the processor during the execution of the test. These static tests included some degree of randomness, to increase the number of test cases and to achieve a greater degree of test coverage. For example, a test-case generator might choose a random mix of hand-generated fixed scripts, and insert random parameter values in the scripts. However, static verification methods required painstaking human composition and verification of long, multilevel queries, so they were extraordinarily time-consuming. Even with random selection of scripts and random values for script parameters, the inability to take into account intermediate processor states meant that certain real-life combinations simply went untested. As processors became more complex, the effort required to design and conduct static verification testing increased exponentially, even as the achievable test coverage declined dramatically.
Consequently, the industry has moved toward the use of dynamically generated, biased pseudo-random test patterns, which can automatically and quickly create an efficient, robust test environment for complex sequential circuits such as processors. In dynamic testing, instructions are generated, all processor resources and facilities needed for executing the instruction are identified and initialized if required, the execution of the instruction is simulated on a model of the design under test, and state is updated to reflect the execution results. The process then iterates, and each instruction generated at the beginning of each iteration is generated with knowledge of the processor state that resulted from the last step executed. Although there are differences in the details of how instructions are generated from test method to test method, in general, instructions are selected for generation using some version of a pseudo-random number generator. Those skilled in the art are generally familiar with the various current methods used to generate and use pseudorandom numbers to support functional verification of complex circuits using dynamically generated biased psuedo-random test patterns.
The relative ease of creating dynamically generated random test programs, combined with the potential for verification bottlenecks, has led logic designers to initiate design verification efforts early in the design process. However, developing appropriate tests using a test generator early, while the design effort is still progressing, requires a significant degree of design flexibility and documentary discipline. Frequent changes to both the test generator and the simulation model are typical, because the system architecture may not be firm, and because implementation-specific details of the test programs are ordinarily decided as the system design progresses. When either the test generator or simulation model is modified, designers typically perform some degree of regression testing, wherein past test patterns are regenerated, rerun, and the results compared, to ensure that no new problems are created by the updates. Also, designers may find it useful to maintain and rerun certain highly successful test patterns from time to time, particularly when a test pattern has been generated that specifically targets a certain function, or is exceptionally complex, or has been determined to provide exceptionally good coverage. Consequently, test patterns must be stored in a library to support regression testing and ongoing design verification efforts.
Rather than storing an entire test pattern, which would require significant storage space, test patterns are saved by storing their control parameters and past results. Control parameters associated with a particular test pattern will typically include some sort of identifying indicia for handling the test pattern in the test library, comments explaining the purpose of the test, the starting seed for the random number generator, and any other externally provided initial conditions to regenerate the program when required. Ordinarily, saving the control parameters of a test pattern is sufficient to assure that the test pattern can be faithfully recreated when required.
However, problems may arise when a test generator, or the simulation model that the generator is using, includes multiple calls to a random number generator for random numbers to perform various aspects of the test generation. In order for a specific test identified by specific control parameters to be repeatable, the random numbers supplied to the test generator must be supplied identically, in response to the same call from the generator or the model every time the test is initiated. Consequently, either the specific order of the test generator""s calls for random numbers must be maintained across generator/model software versions, or the specific number that is supplied to the test generator or model in response to each specific call must be maintained across software versions. Absent one of these controls, a particular test identified by certain control parameters may not be repeatable in a test generator that includes multiple calls for random numbers if new calls are inserted. This occurs because the number generator will always generate the same sequence of numbers in the same order in response to the seed contained within the test control parameters.
To illustrate the problem, assume a test generator generating verification tests for a processor under design generates and runs a test pattern P1 that includes random number seed S1. Suppose that the generator first requests a random number to use in selecting an instruction, then a sequence of four random numbers to use in initializing four registers, then a sequence of five random numbers that it uses to preload the cache. Thereafter, the test generator generates the instruction, simulates its execution on the model, and updates state. Table 1 below shows the sequence of random numbers as they are generated and supplied to the various functions of the test generator.
Assume now that the design is modified to include an additional four registers, triggering a test generator update to initialize those additional four registers. As modified, the generator now first requests a random number to use in selecting an instruction, then a sequence of eight random numbers to use in initializing eight registers, then a sequence of five random numbers that it uses to preload the cache. Table 2 below shows the sequence of random numbers that would be supplied to the test generator if test pattern P1 having random number seed S1 is run on the modified generator. As shown in Table 2, the first ten random numbers shown in Table 1 will be generated in the same order as shown in Table 1. However, the first time P1 was generated, the cache was initialized using R6-R10. After the modification, R6-R9 is used to initialize the new registers, and the cache is initialized using R10-R14. Consequently, the cache contents will be different when P1 is run on the modified test generator, the test results will be different, and although none of P1xe2x80x2s control parameters were changed, the test is not repeatable.
The present invention solves this problem by providing an apparatus and method that insures that the same random numbers are always provided to a computer program such as a test generator or simulation model, in response to the same call in which they were first provided, every time a test that includes a particular seed number for the random number generator is run, regardless of whether the program has been modified. Consequently, the present invention insures that tests and other executable programs that require random numbers to be generated from a specific seed and supplied to the program are repeatable across multiple versions and upgrades of the software.
The present invention comprises a random number indexing method and apparatus that eliminates the link between the specific random number provided to a computer program and the relative location in the program of its corresponding call. The present invention includes a pseudo-random number generator that generates a sequence of pseudo-random numbers in response to a seed, an index array that uniquely identifies each generated pseudo-random number with an identifying indicia in a one-to-one correspondence, and a computer program that uses the identifying indicia in the index array to call for and receive pseudo-random numbers. In some embodiments, the index array is included in the computer program. In some embodiments, upon initialization, the computer program provides the seed value to the pseudo-random number generator and then populates the index array.